<!DOCTYPE html>
<html>
<head>
  <title>A* Pathfinding Demo</title>
  <style>
    canvas {
      border: 1px solid #000;
    }
  </style>
</head>
<body>
  <canvas id="myCanvas" width="400" height="400"></canvas>

  <script>
    var canvas = document.getElementById('myCanvas');
    var ctx = canvas.getContext('2d');
    
    // 定义节点类
    class Node {
      constructor(x, y, isObstacle) {
        this.x = x;
        this.y = y;
        this.isObstacle = isObstacle;
        this.g = 0; // 从起点到当前节点的实际代价
        this.h = 0; // 从当前节点到目标节点的估计代价
        this.f = 0; // f = g + h
        this.parent = null; // 用于记录路径
      }
    }

    // 启发式函数，这里使用曼哈顿距离
    function heuristic(node, end) {
      return Math.abs(node.x - end.x) + Math.abs(node.y - end.y);
    }

    // A*算法
    function astar(start, end, grid) {
      var openList = [];
      var closedList = [];

      openList.push(start);

      while (openList.length > 0) {
        // 找到 f 值最小的节点
        var currentNode = openList[0];
        var currentIndex = 0;
        for (var i = 1; i < openList.length; i++) {
          if (openList[i].f < currentNode.f) {
            currentNode = openList[i];
            currentIndex = i;
          }
        }

        // 将当前节点从开放列表中移除，并加入关闭列表
        openList.splice(currentIndex, 1);
        closedList.push(currentNode);

        // 找到路径
        if (currentNode.x === end.x && currentNode.y === end.y) {
          var path = [];
          var current = currentNode;
          while (current !== null) {
            path.push({ x: current.x, y: current.y });
            current = current.parent;
          }
          return path.reverse();
        }

        // 生成相邻节点
        var neighbors = [];
        var dx = [-1, 0, 1, 0]; // 上下左右
        var dy = [0, 1, 0, -1];
        for (var i = 0; i < 4; i++) {
          var newX = currentNode.x + dx[i];
          var newY = currentNode.y + dy[i];
          if (newX >= 0 && newX < grid.length && newY >= 0 && newY < grid[0].length && !grid[newX][newY].isObstacle) {
            neighbors.push(grid[newX][newY]);
          }
        }

        for (var j = 0; j < neighbors.length; j++) {
          var neighbor = neighbors[j];

          // 如果相邻节点在关闭列表中，跳过
          if (closedList.some(node => node.x === neighbor.x && node.y === neighbor.y)) {
            continue;
          }

          // 计算代价
          var gScore = currentNode.g + 1; // 假设移动到相邻节点的代价为1
          var hScore = heuristic(neighbor, end);
          var fScore = gScore + hScore;

          // 如果相邻节点不在开放列表中，加入开放列表
          if (!openList.some(node => node.x === neighbor.x && node.y === neighbor.y)) {
            neighbor.g = gScore;
            neighbor.h = hScore;
            neighbor.f = fScore;
            neighbor.parent = currentNode;
            openList.push(neighbor);
          }
        }
      }

      // 如果开放列表为空，且没有找到路径，返回空数组
      return [];
    }

    // 创建地图
    var grid = [];
    var rows = 10;
    var cols = 10;
    for (var i = 0; i < rows; i++) {
      grid[i] = [];
      for (var j = 0; j < cols; j++) {
        // 在这里根据实际情况定义障碍物
        var isObstacle = Math.random() < 0.3; // 30% 的概率设置为障碍物
        grid[i][j] = new Node(i, j, isObstacle);
      }
    }

    // 定义起点和终点
    var start = grid[0][0];
    var end = grid[rows - 1][cols - 1];

    // 调用A*算法，获取最佳路径
    var path = astar(start, end, grid);
    console.log(path);

    // 绘制地图和路径
    var nodeSize = 40;
    canvas.width = cols * nodeSize;
    canvas.height = rows * nodeSize;

    for (var i = 0; i < rows; i++) {
      for (var j = 0; j < cols; j++) {
        var node = grid[i][j];
        ctx.beginPath();
        ctx.rect(j * nodeSize, i * nodeSize, nodeSize, nodeSize);
        if (node.isObstacle) {
          ctx.fillStyle = 'black';
        } else {
          ctx.fillStyle = 'white';
        }
        ctx.fill();
        ctx.stroke();
      }
    }

    for (var k = 0; k < path.length; k++) {
      var pathNode = path[k];
      ctx.beginPath();
      ctx.rect(pathNode.y * nodeSize, pathNode.x * nodeSize, nodeSize, nodeSize);
      ctx.fillStyle = 'green';
      ctx.fill();
      ctx.stroke();
    }
  </script>
</body>
</html>
